//SamXIAO
#include <bits/stdc++.h>
using namespace std;
#define szCNT_OF(x) (sizeof(x) / sizeof(x[0]))
#define MAX_LEN 5086  // 10 * 1000 * 1000 + 86

#define RRR 12345
void v1(int n) {
   long long f[MAX_LEN] = {0, 8};

   //f[n] = 8f[n-1] + 9*10^(n-2)
   long long p10 = 1;
   for (int i = 2; i <= n; i++) {
      f[i] = (8 * f[i - 1] + 9 * p10) % RRR;
      p10 *= 10;
      p10 %= RRR; // !!!
   }

   printf("%d", f[n]);
}

void v2(int n) {
   long long f[MAX_LEN] = {0, 1};
   long long g[MAX_LEN] = {0, 8};

   for (int i = 2; i <= n; i++) {
      f[i] = (g[i - 1] + f[i - 1] * 9) % RRR;
      g[i] = (f[i - 1] + g[i - 1] * 9) % RRR;
   }

   printf("%d", g[n]);
}

void work1() {
   int n;
   scanf("%d", &n);
   v1(n);
   //v2(n);
}
int main() {
   work1();
   return 0;
}
